第55章 简单动态规划

动态规划(Dynamic Programming,简称DP)是一种通过分解复杂问题为重叠子问题，并利用子问题的解来高效求解原问题的算法思想。与递归相比，动态规划通过存储中间结果（即"记忆化"）避免了重复计算，显著提升了效率。

55.1 动态规划的基本概念

55.1.1 核心思想

动态规划的核心思想可概括为"分解问题、存储中间结果、利用子问题解求原问题解"：

1. 重叠子问题：子问题之间存在重复，不同原问题拆分后会出现相同子问题。
2. 最优子结构：原问题的最优解由子问题最优解构成，是DP成立基础。
3. 状态转移方程：描述当前状态与前置状态的数学关系式。
4. 边界条件：最小、无法再拆分的子问题解，作为计算起点。

55.1.2 解题标准步骤

1. 定义状态：确定dp[i]/dp[i][j]代表的实际含义
2. 推导状态转移方程
3. 初始化边界条件
4. 按依赖顺序迭代计算所有状态
5. 从dp数组提取最终答案

55.2 一维动态规划

一维DP状态仅使用单下标dp[i]，适合线性递推类问题。

55.2.1 斐波那契数列

问题定义： $F(0)=0$ $F(1)=1$ $F(n)=F(n-1)+F(n-1) \quad n≥2$ 求第$n$项数值。

动态规划解法： 状态定义：$dp[i]$表示第$i$个斐波那契数 转移方程：$dp[i] = dp[i-1] + dp[i-2]$ 边界：$dp[0]=0,\quad dp[1]=1$

#include <vector>
using namespace std;
int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

空间优化（仅保留两个前置变量，空间复杂度降至$O(1)$）

int fibonacciOptimized(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

55.2.2 爬楼梯问题

题意：每次可爬1阶或2阶，求登上$n$阶楼梯总方法数。 状态：$dp[i]$爬到第$i$阶的方法数 转移：$dp[i] = dp[i-1] + dp[i-2]$ 边界：$dp[1]=1,\quad dp[2]=2$

int climbStairs(int n) {
    if (n == 1) return 1;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

55.2.3 最大子数组和

题意：给定整数数组，找出连续子数组的最大和（子数组至少一个元素） 状态：$dp[i]$以第$i$个元素结尾的最大连续和 转移：$dp[i] = \max(nums[i], dp[i-1]+nums[i])$ 边界：$dp[0] = nums[0]$ 答案：dp数组内全部数值的最大值

#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }
    return maxSum;
}

空间优化版本

int maxSubArrayOptimized(vector<int>& nums) {
    int n = nums.size();
    int currentMax = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < n; i++) {
        currentMax = max(nums[i], currentMax + nums[i]);
        maxSum = max(maxSum, currentMax);
    }
    return maxSum;
}

55.3 简单背包问题

55.3.1 01背包

题意：共$n$件物品，每件仅取一次；物品重量$w[i]$、价值$v[i]$，背包最大容量$C$，求可装入最大总价值。 状态：$dp[i][j]$前$i$件物品，容量$j$时最大价值 转移： $dp[i][j] = \max(dp[i-1],\ j≥w[i] ? dp[i-1][j-w[i]]+v[i] : 0)$ 边界：$dp[0][j]=0,\quad dp[i][0]=0$ 最终结果：$dp[n][C]$

#include <vector>
#include <algorithm>
using namespace std;
int knapsack01(vector<int>& w, vector<int>& v, int C) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(C + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= w[i - 1]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return dp[n][C];
}

一维空间优化（逆序遍历，防止重复选取）

int knapsack01Optimized(vector<int>& w, vector<int>& v, int C) {
    int n = w.size();
    vector<int> dp(C + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = C; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[C];
}

55.3.2 完全背包

题意：每件物品可无限选取，其余条件同01背包。 核心区别：遍历顺序改为正序，允许重复选取。 一维状态：$dp[j]$容量$j$的最大价值 转移：$dp[j] = \max(dp[j], dp[j-w[i]]+v[i])$

int completeKnapsack(vector<int>& w, vector<int>& v, int C) {
    int n = w.size();
    vector<int> dp(C + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = w[i]; j <= C; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[C];
}

01背包与完全背包对比：

1. 01背包：容量从大到小遍历，每件物品只能选1次
2. 完全背包：容量从小到大遍历，每件可无限选取

55.4 动态规划常见优化策略

1. 空间优化：二维dp压缩为一维，或只用少数变量存储前置状态（斐波那契、最大子数组）
2. 滚动数组：仅保留最近k层状态，大幅降低空间开销
3. 状态压缩：合并冗余状态，减少dp数组维度
4. 剪枝：提前跳过不可能产生更优解的分支（如路径和超过目标直接终止）